#include <stdio.h>

void swap(int* a, int* b);

void quickSort(int arr[], int head, int tail);

int main(int argc, const char* argv[]) {
	int arr[]={2,5,3,7,4,12,5};
	int n = sizeof(arr)/sizeof(int);	
	
	fprintf(stdout, "Before: ");
	for (int i = 0; i < n; ++i) {
		fprintf(stdout, "%d ", arr[i]);
	}

	quickSort(arr, 0, n - 1);

	fprintf(stdout, "\nAfter: ");
	for (int i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	return 0;
}

void swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void quickSort(int* arr, int head, int tail) {
	int i = head;
	int j = tail;
	int key = arr[head];
	while (i < j) {
		while (i < j && arr[j] >= key) --j;
		while (i < j && arr[i] <= key) ++i;
		if (i < j) swap(&arr[i], &arr[j]);	
	}
	swap(&arr[head], &arr[i]);
	if (i - 1 > head) quickSort(arr, head, i - 1);
	if (i + 1 < tail) quickSort(arr, i + 1, tail);
}
